This section is intended to provide a background or context to the invention that is recited in the claims. The description herein may include concepts that could be pursued, but are not necessarily ones that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, what is described in this section is not prior art to the description and claims in this application and is not admitted to be prior art by inclusion in this section.
Mesh networks can be used to route data, voice and instructions between individual nodes. Mesh networking allows for continuous connections and reconfigurations around broken or blocked paths by “hopping” from one node to another until a desired destination is reached. In mesh networks, component parts can connect to each other via multiple hops. Mesh networks are also “self-healing” in the sense that, even when a node becomes inoperable and/or unusable for some reason, the network can still operate by reconfiguring the hop path. FIG. 1 is a representation of a plurality of nodes 100 which are configured to form one such mesh network 110.
Mesh networks are being deployed in a wide range of situations and can often be used in place of cellular network architectures. One particular application for mesh networks involves using the networks for backhauling metropolitan wireless networks of WiFi access points. A well-engineered mesh network for the backhaul is the basis for the successful implementation of such networks.
It is preferable that such mesh networks be operable within WiFi frequency bands for the access traffic. However, 802.11 Media Access Control (MAC) performs poorly in mesh networks for backhaul traffic. This poor performance is due to the high overhead of congestion management and channel acquisition. Nodes in wireless mesh networks cannot transmit simultaneously without interfering with each other. This reduces the overall performance of the air interface by adding a delay to “win” a contention for the channel, and by reducing bandwidth due to the time division of the channel between different users.
For the above reasons, a number of scheduling protocols have been designed for allocating transmission time slots to each node in the backhaul mesh network. In one such time-division multiple access system, during a time slot allocated to a transmission, both the sender and the transmitter can communicate free from interference, as the other potentially interfering users are not permitted to transmit during this time slot.
Another method for arbitrating the contention of the medium is to reduce the number of accesses to the channel. Network coding reduces the number of transmitted packets by encoding two packets at a relay point in the network. A basic type of such an architecture is as follows. In a backhaul network consisting of A, B and a gateway G, if A sends a packet P1 to G, and G sends a packet P2 to A, then B will relay the packets. In this situation, the total number of channel access is four (one for P1 from A to B, one from B to G, and, in the other direction, one for P2 from G to B and one from B to A). In its most basic form, network coding suggests that, after receiving P1 from A and P2 from G, B should broadcast P1xP2 (where x denotes the XOR operation) to both A and G. A and G can then each recover P2 and P1 respectively, based on the packet they sent to B and the packet they received from B. The number of channel accesses is reduced from 4 to 3, leveraging the broadcast nature of the air interface. This type of network coding is discussed, for example in “XOR in the air: practical network coding, Katti et al, Sigcomm 2006.” However, implementation of this type of system can lead to potential “fairness” issues.